import java.util.Arrays;
import java.util.*;

public class Day17 {
    public static void main(String[] args) {
        int[][] arr = {{4,5},{2,3},{0,1}};
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] > o2[0])
                    return 1;
                else if(o1[0] == o2[0])
                    return 0;
                else
                    return -1;
            }
        });

        System.out.println(arr);
    }
    //646.最长数对连
    public int findLongestChain(int[][] pairs) {
        //1.排序
        Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] > o2[0])
                    return 1;
                else if(o1[0] == o2[0])
                    return 0;
                else
                    return -1;
            }
        });
        int n = pairs.length;
        int[] dp = new int[n];
        for(int i=0;i<n;i++) {
            dp[i]=1;
        }
        int ret = 1;
        for(int i=1;i<n;i++) {
            for(int j=i-1;j>=0;j--) {
                if(pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
    //1218.
    public int longestSubsequence(int[] arr, int difference) {
        //1.初始化
        int n = arr.length;//以i结尾的最长等差子序列
        int[] dp = new int[n];
        int ret = 1;
        dp[0]=1;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(arr[0],1);
        //2.填表
        for(int i=1;i<n;i++) {
            dp[i]=1;
            if(map.getOrDefault(arr[i]-difference,0) !=0 ) {
                dp[i]=map.get(arr[i]-difference)+1;
                map.put(arr[i],dp[i]);
            }else {
                map.put(arr[i],1);
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}
